package com.datastructures2.graph.无向图;


/**
 * 深度优先遍历(无向图)
 */
public class DepthFirstSearch {
    private boolean[] marked;    // marked[v] = is there an s-v path?
    private int count;           // number of vertices connected to s


    public DepthFirstSearch(Graph G, int s) {
        marked = new boolean[G.V()];
        validateVertex(s);
        dfs(G, s);
    }



    private void dfs(Graph G, int v) {
        count++;
        marked[v] = true;

        System.out.print(v+"--->");
        for (int w : G.adj(v)) {
            if (!marked[w]) {
                dfs(G, w);
            }
        }
    }


    public boolean marked(int v) {
        validateVertex(v);
        return marked[v];
    }

    public int count() {
        return count;
    }

    private void validateVertex(int v) {
        int V = marked.length;
        if (v < 0 || v >= V)
            throw new IllegalArgumentException("vertex " + v + " is not between 0 and " + (V-1));
    }

    public static void main(String[] args) {
        Graph graph=new Graph(6);
        graph.addEdge(0,2);
        graph.addEdge(0,1);
        graph.addEdge(0,5);
        graph.addEdge(2,1);
        graph.addEdge(2,3);
        graph.addEdge(2,4);
        graph.addEdge(3,5);
        graph.addEdge(3,4);
        DepthFirstSearch dfs=new DepthFirstSearch(graph,0);


    }


}